package stu.edu.InterviewQuestion;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Random;

public class FindMinK {

    public static void main(String[] args) {
        FindMinK minK = new FindMinK();
        int[] arr = new int[]{4,6,3,5,4,8,7,0,0,0,1,2,0,7,-1,-2};
        List<Integer> res = minK.GetLeastNumbers_Solution(arr, 6);
        System.out.println(Arrays.toString(res.toArray()));
    }

    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if(input == null || input.length < k || k <= 0) {
            return list;
        }
        int left = 0, right = input.length - 1;
        int index = partation(input, left, right);
        while(index != k-1) {
            if(index > k-1) {
                index = partation(input, left, index-1);
            }else {
                index = partation(input, index+1, right);
            }
        }
        for(int i=0; i<k; i++) {
            list.add(input[i]);
        }
        return list;
    }

    private int partation(int[] arr, int start, int end) {
        int index = new Random().nextInt(end - start + 1) + start;
        swap(arr, index, end);
        int small = start - 1;
        for (index = start; index < end; index++) {
            if(arr[index] < arr[end]) {
                small++;
                if(small != index) {
                    swap(arr, index, small);
                }
            }
        }
        small++;
        swap(arr, small, end);
        return small;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}
